#pragma once

#include  "iostream"
#include  "vector"
#include  "stack"
#include  "unordered_map"
#include   "queue"

using namespace std;

/*
 * 给你一个整数 n ，按字典序返回范围 [1, n] 内所有整数。

你必须设计一个时间复杂度为 O(n) 且使用 O(1) 额外空间的算法。



示例 1：

输入：n = 13
输出：[1,10,11,12,13,2,3,4,5,6,7,8,9]
示例 2：

输入：n = 2
输出：[1,2]
 * */
//算是抄的类似雨440题
vector<int> lexicalOrder(int n) {
    vector<int> res(n);
    long num = 1;
    for (int i = 1; i <= n; i++) {
        res[i - 1] = num;

        if (num * 10 <= n) {
            num = num * 10;
            continue;
        } else {
            while (num + 1 > n || num % 10 == 9) {
                num = num / 10;
            }
            num++;
        }
    }


    return res;

}

vector<int> lexicalOrder(int n) {
    vector<int> res(n);
    for (int i = 1; i <= n; ++i) {
        res[i - 1] = i;
    }

    sort(res.begin(), res.end(), [&](int &a, int &b) {
        return to_string(a) < to_string(b);
    });


    return res;

}